/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package algoritms;

/**
 *
 * @author Patronus
 */
public class KnutaMorisaPratta {

    private int counter = 1;
    private int i = 0;
    private int[] prefixFunc;

    int[] getPrefixFunc(String pattern) {
        prefixFunc = new int[pattern.length()];
        char[] str = pattern.toCharArray();


        for (char ex : str) {

            if (ex == str[counter]) {
                counter++;
                prefixFunc[i] = counter;
            } else {
                counter = 0;
                prefixFunc[i] = 0;
            }
            i++;
        }

        return prefixFunc;
    }

    public void kmp(String text, String pattern) {
        int prefix[] = getPrefixFunc(pattern);
               
        char[] t = text.toCharArray();
        char[] p = pattern.toCharArray();
        int n = text.length();
        int j = 0;
        int m = pattern.length();
        for (int k = 0; k < n; k++) {
            while (true) {
                if (t[k] == p[j]) {
                    j++;
                    if (j == m) {
                        System.out.println("Position :" + (k));
                        j = prefix[0];
                    }
                    break;
                } else if (j == 0) {
                    break;
                } else {
                    j = prefix[j];
                }
            }

        }
    }
}
